
/*
回溯
连接：https://leetcode.cn/problems/max-area-of-island/submissions/
题目：岛屿的最大面积


  
3. 算法思路：
• 遍历整个矩阵，每当遇到⼀块⼟地的时候，就⽤「深搜」或者「宽搜」将与这块⼟地相连的「整个
岛屿」的⾯积计算出来。
• 然后在搜索得到的「所有的岛屿⾯积」求⼀个「最⼤值」即可。
• 在搜索过程中，为了「防⽌搜到重复的⼟地」：
◦ 可以开⼀个同等规模的「布尔数组」，标记⼀下这个位置是否已经被访问过；
◦ 也可以将原始矩阵的 1 修改成 0 ，但是这样操作会修改原始矩阵。
4. 解法（深搜 dfs）：
算法流程：
• 主函数内：
a. 遍历整个数组，发现⼀块没有遍历到的⼟地之后，就⽤ dfs ，将与这块⼟地相连的岛屿的⾯
积求出来；
b. 然后将⾯积更新到最终结果 ret 中。
• 深搜函数 dfs 中：
a. 能够进到 dfs 函数中，说明是⼀个没遍历到的位置；
b. 标记⼀下已经遍历过，设置⼀个变量 S = 1 （当前这个位置的⾯积为 1 ），记录最终的⾯
积；
c. 上下左右遍历四个位置：
▪ 如果找到⼀块没有遍历到的⼟地，就将与这块⼟地相连的岛屿⾯积累加到 S 上；
d. 循环结束后， S 中存的就是整块岛屿的⾯积，返回即可

   
    
*/
class Solution {
public:
    
    bool vis[51][51];
    int m,n;
    int r[4] = {0,0,-1,1};
    int c[4] = {-1,1,0,0};
    int sum=0;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size();
        n =grid[0].size();
        int ret = 0;
        for(int i =0;i<m;i++)
        {
            for(int j =0;j<n;j++)
            {
                if(!vis[i][j]&&grid[i][j]==1)
                {
                    sum=0;
                    dfs(grid,i,j);
                    ret = max(ret,sum);
                }
            }
        }
        return ret;
    }

    void dfs(vector<vector<int>>& grid,int i,int j)
    {
        vis[i][j] = true;
        sum++;
        for(int k=0;k<4;k++)
        {
            int x = i+r[k];
            int y = j+c[k];
            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && grid[x][y]==1 )
            {
                dfs(grid,x,y);
            }
        }
    }
};